package utils;

public class BinarySearchWithUnknownDuplicates {
    public static int[] searchRange(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int[] result = {-1, -1};

        // 二分查找目标元素
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                result[0] = mid;
                result[1] = mid;
                break;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        // 如果未找到目标元素，直接返回
        if (result[0] == -1) {
            return result;
        }

        // 确定左边界
        int tempLeft = result[0];
        while (tempLeft >= 0 && nums[tempLeft] == target) {
            tempLeft--;
        }
        result[0] = tempLeft + 1;

        // 确定右边界
        int tempRight = result[1];
        while (tempRight < nums.length && nums[tempRight] == target) {
            tempRight++;
        }
        result[1] = tempRight - 1;

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 2, 3, 3, 4, 5, 5, 5, 6};
        int target = 1;
        int[] range = searchRange(nums, target);
        if (range[0]!= -1 && range[1]!= -1) {
            System.out.println("目标元素 " + target + " 的左右边界为：[" + range[0] + ", " + range[1] + "]");
        } else {
            System.out.println("目标元素 " + target + " 在数组中不存在。");
        }
    }
}
